#include <iostream>
#include <vector>
using namespace std;

// https://gitee.com/link?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fsearch-insert-position%2F
int searchInsert(vector<int> &nums, int target)
{
    int left = 0, right = nums.size() - 1;
    if (right < 0)
        return left;
    while (left < right) // 同样二段性，分为[小于target块][大于等于target块]
    {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target)
            left = mid + 1;
        else
            right = mid;
    }
    if (nums[right] < target) //[全部小于target块]
        return right + 1;
    return left;
}

// https://gitee.com/link?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fsqrtx%2F
int mySqrt(int x)
{
    if (x <= 1) // 对x<=1做特殊处理避免x=1时，left和right都取0；
        return x;
    int left = 0, right = x / 2;
    while (left < right) // 同样二段性，分为[小于等于x块（x的算术根只会出现在这一块）][大于x块]
    {
        long mid = left + (right - left + 1) / 2;
        if ((mid * mid) > x)
            right = mid - 1;
        else
            left = mid;
    }
    return left;
}

//https://gitee.com/link?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Ffind-peak-element%2F
int peakIndexInMountainArray(vector<int> &arr)
{
    int left = 0, right = arr.size() - 1;
    while (left < right)
    {
        int mid = left + (right - left + 1) / 2;
        if (arr[mid] > arr[mid - 1] && arr[mid] < arr[mid + 1])//根据mid前后数据的大小进行比较查找
        {
            left = mid + 1;
        }
        else if (arr[mid] < arr[mid - 1] && arr[mid] > arr[mid + 1])
        {
            right = mid - 1;
        }
        else
        {
            return mid;
        }
    }
    return left;
}
